package com.zj.alm;

public class MaxValue {
    public static int maxValue(int[] values,int[] neetPeople,int maxPeople){
       int[][] dp = new int[values.length+1][maxPeople+1];
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= maxPeople; j++) {
                //选择的物品超过最大承重
                if(neetPeople[i-1]>j){
                    //不能选择的物品，等于上轮的最大承重
                    dp[i][j]=dp[i-1][j];
                }
                //选择的物品不超过最大承重
                else{
                    //选择该物品后的最大价值
                    int currentValue= values[i-1]+dp[i-1][j-neetPeople[i-1]];
                    //上轮的最大值
                    int proValue = dp[i-1][j];
                    dp[i][j]=Math.max(proValue,currentValue);
                }
            }
        }

        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print("  "+dp[i][j]+"\t");
            }
            System.out.println();
        }

        int mv = dp[values.length][maxPeople-2];
        int restPeople= maxPeople;
        String numStr = "";
        for (int i= values.length;i>0;i--){
            if(dp[i][restPeople]>dp[i-1][restPeople]){
                numStr = i+ " " + numStr;
                restPeople=restPeople-neetPeople[i-1];
            }
            if(restPeople==0){
                break;
            }
        }
        System.out.println("选择的金矿有："+numStr);
        return mv;
    }

    public static void main(String[] args) {
        int[] values = {60,30,50,40,60};
        int [] weights ={2,2,6,5,4};
        int max =10;
        int i = maxValue(values, weights, max);
        System.out.println(i);
    }

}
